package com.pitaya.avatar.service.impl;

public class UnionFindSet{
			
	public Node find(Node node){
		Node root = node;
		Node parent = node.getParent();
		while(parent != null){
			root = parent;
			parent = parent.getParent();
		}
		parent = node.getParent();
		while(parent != null){
			node.setParent(root);
			node = parent;
			parent = node.getParent();
		}
		return root;
	}
	
	public void union(Node root1, Node root2){
		int childSize = root2.getChildsSize()+root1.getChildsSize();
		if(root1.getChildsSize() < root2.getChildsSize()){
			root1.setParent(root2);
			root2.setChildsSize(childSize);
		} else {
			root2.setParent(root1);
			root1.setChildsSize(childSize);
		}
	}
}
